The S3 group is the group of permutation on 3 elements. It has 6 elements. It is the group of all the automorphism on the set {1, 2, 3}.
Here is the full list of the elements of S3:
## e: ()
## a: (1,2)
## b: (1,3)
## c: (2,3)
## p: (1,2,3)
## p^2: (1,3,2)
Table of S3:
| S3 | e | p | p2 | a | b | c |
|---|---|---|---|---|---|---|
| e | e | p | p2 | a | b | c |
| p | p | p2 | e | c | a | b |
| p2 | p2 | e | p | b | c | a |
| a | a | b | c | e | p | p2 |
| b | b | c | a | p2 | e | p |
| c | c | a | b | p | p2 | e |
Order of the elements:
| S3 | Order | Sign | Inversions |
|---|---|---|---|
| e | 1 | + | 0 |
| p | 3 | + | 0 |
| p2 | 3 | + | 0 |
| a | 2 | - | 1 |
| b | 2 | - | 1 |
| c | 2 | - | 1 |
Unique normal chain decomposition of S3:
\[ C(2) \lhd C(3) \lhd S_3\]
And this decomposition is unique, the factors cannot be swapped.
grViz('
graph cycle {
graph[layout = neato]
node [shape = circle, style = filled, color = grey, label=""]
e [color = red]; a; b; c; p; p2
e -- a
e -- b
e -- c
e -- p -- p2 -- e
}
')
The group <p> = {e, p, p2} is normal in S3:
all(p^a == p2, p^b == p2, p^c == p2)
## [1] TRUE
The classes of <p> in S3 are:
{e, p, p2}, {a, b, c}
The action of a on <p>: (p p2)
More detailed action of the group on <p>:
| S3 | {e, p, p2} | {a, b, c} |
|---|---|---|
| e | {e, p, p2} | {a, b, c} |
| a | {a, b, c} | {e, p, p2} |
| b | {b, c, a} | {p2, e, p} |
| c | {c, a, b} | {p, p2, e} |
| p | {p, p2, e} | {c, a, b} |
| p2 | {p2, e, p} | {b, c, a} |
<p> is isomorphic to Z/3Z and it has no non-trivial subgroups.
If G is a subgroup of S3 containing <p> then G*<p> is a subgroup of S3/<p>. S3/<p> is a group of order 2 so it is isomorphic to Z/2Z and it has no non trivial subgroup. The only subgroups containing p are {e} and S3.
If G is a sub-group not including <p>. Then inter(G, <p>) is {e}. because inter(G, <p>) is a subgroup of <p> and it cannot be <p> because G does no include <p>.
So G is included in {e, a, b, c}. G cannot contain more than 2 elements because any of products ab, bc, … will yield an element of <p>. So G is either {e, a}, {e, b}, {e, c}.
Conclusion: Here is the full list of the subgroups of S3: {e}, {e, a}, {e, b}, {e, c}, {e, p, p2}, {e, a, b, c, p, p2}
Lattice of all the subgroups
## Warning in .Call("R_igraph_layout_fruchterman_reingold", graph, coords, :
## '.Random.seed' is not an integer vector but of type 'NULL', so ignored
Normal subgroups
This is a faithful action.
We can compute the orbits:
| S3 | Orbits |
|---|---|
| e | {1} {2} {3} |
| a | {1, 2} {3} |
| b | {1, 3} {2} |
| c | {1} {2, 3} |
| p | {1, 2, 3} |
| p2 | {1, 2, 3} |
We can also compute the stabilizers:
| {1, 2, 3} | Stabilizer |
|---|---|
| 1 | <c> |
| 2 | <b> |
| 3 | <a> |
We consider the action of S3 on this set: {{1, 2}, {1, 3}, {2, 3}}
## [1] TRUE
all(
a_f(c(1, 2)) == c(2, 1),
a_f(c(1,3)) == c(2, 3),
a_f(c(2, 3)) == c(1, 3))
## [1] TRUE
Since a and p generate S3 we deduce that the action is faithfull.
Orbits
| S3 | Orbits |
|---|---|
| e | {1_2} {1_3} {2_3} |
| a | {1_2} {1_3, 2_3} |
| b | {1_2, 2_3} {1_3} |
| c | {1_2, 1_3} {2, 3} |
| p | {1_2, 2_3, 1_3} |
| p2 | {1_2, 2_3, 1_3} |
Stabilizers
The elements of order 2 are: a, b, c
c(a^p == c, a^(p^2) == b)
## [1] TRUE TRUE
So the action is transitive. And |O(a)|.|Stab(a)| = 6 => 3.|Stab| = 6 So the stabilizer size is 2.
And:
| S3 | Stab |
|---|---|
| a | e, a |
| b | e, b |
| c | e, c |
The elements of order 3 are: p, p^2
c(p^a == p^2)
## [1] TRUE
So the action is transitive and: |O(p)|.|Stab(p)| = 6 so |Stab(p)| = 2
| S3 | Stab |
|---|---|
| p | e, p, p2 |
| p2 | e, p, p2 |
Let f be a recording, and p a permutation of the indices of the recording. f’ is the image of f by p if the index 2 of f’ is the index i of f such that p(i) = 2. So \(i = p^{-1}(2)\)
Let’s write a function that applies a permutation to a recording.
apprec <- function(gp) {
function(...) {
f <- c(...)
f[as.word(gp) %>% unclass %>% c]
}
}
S3 has an action on
| Beat | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | x | x | x | x | x | x |
| 2 | x | x | x | x | x | x |
| p.1 | 1 | 2 | 3 | 4 | 5 | 6 |
| p.2 | 3 | 1 | 2 | 6 | 4 | 5 |
| a.1 | 4 | 5 | 6 | 1 | 2 | 3 |
| a.2 | 1 | 2 | 3 | 4 | 6 | 5 |
| p2.2 | 2 | 3 | 1 | 5 | 6 | 4 |
| apa.2 | 3 | 1 | 2 | 5 | 6 | 4 |
This convention means that the action of p.2 is given by 1 -> 3, 2 -> 1, 3 -> 2… And \((p \bullet f)_i = f_{p(i)}\) So that (pf)(1) = f(2). So it we want to know where the value at index 1 is sent we need to find where is the 1 on the p line. So here it is at index 2. That means the value at 1 is taken to index 2. e.g pf(2) = f(1). So that’s how to read this.
However this is not an action because:
\((g h \bullet f)_i = f_{gh(i)} = f_{h(g(i))} = (h \bullet g \bullet f)_i\) so \(g h \bullet f = h \bullet g \bullet f\)
However we have
\(f \bullet g h = f_{gh(i)} = f_{h(g(i))} = (f \bullet g \bullet h)_i\) so \(f \bullet g h = f \bullet g \bullet h\)
So it is a ‘contra-action’ and it is given by a morphism \(\phi: S3 \rightarrow S(Rec)^{op}\) Actually \(\phi\) is a composition: \(S3 \rightarrow S(S3) \rightarrow S(Rec)\) Where the first morphism is contravariant and the second one is covariant. So the composition is a contravariant morphism.
The action of p on the first layer is the trivial one. The action of a on the first layer just switches 2 the 2 3-blocks.
The action of p on the second layer circulates the 2 3-blocks. It has 2 orbits. The action of a on the second layer first 3-block is the trivial one. On the second 3-block it switches 5 and 6.
In order to define the action we remember this following presentation of S3: \(<a^2, p^3, apa = p^2>\)
Check that the action on the first row is an action: \(\phi_1(a) = (1 4) (2 5) (3 6)\) \(\phi_1(p) = id\)
The images verify all the relations, so it is indeed an action.
Check that the action on the second row is an action: \(\phi_2(a) = (5 6)\) \(\phi_2(p) = (1 2 3) (4 5 6)\)
gp <- as.cycle(1:3) * as.cycle(4:6)
ga <- as.cycle(5:6)
So apparently this is not an action since gp^ga != gp^2
gp^ga == gp^2
## [1] FALSE
We can try this one:
| Beat | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| a.2 | 4 | 5 | 6 | 1 | 3 | 2 |
We have for the second row:
ga <- as.word(c(4, 5, 6, 1, 3, 2))
This also doesn’t work since ga^2 is not identity.
What about this one?
| Beat | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| p.2 | 2 | 3 | 1 | 5 | 6 | 4 |
| a.2 | 4 | 6 | 5 | 1 | 3 | 2 |
ga <- as.word(c(4, 6, 5, 1, 3, 2))
cat('ga: ', as.character(as.cycle(ga)), '\r\n')
## ga: (1,4)(2,6)(3,5)
cat('gp: ', as.character(as.cycle(gp)))
## gp: (1,2,3)(4,5,6)
We have:
c(gp^3 == as.cycle(),
ga^2 == as.cycle(),
gp^ga == gp^2)
## [1] TRUE TRUE TRUE
So it is an action of S3
| Beat | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| e | 1 | 2 | 3 | 4 | 5 | 6 |
| a | 4 | 6 | 5 | 1 | 3 | 2 |
| p | 2 | 3 | 1 | 5 | 6 | 4 |
| p2 | 3 | 1 | 2 | 6 | 4 | 5 |
| ap | 5 | 4 | 6 | 2 | 1 | 3 |
| ap2 | 6 | 5 | 4 | 3 | 2 | 1 |
Let \(\eta: Rec \rightarrow Rec\) where Rec is the set of all recordings of this action. We let \(\eta(f)_i = 1 + f_i\) That is if \(f_i = 1\) then \(\eta(f)_i = 0\) and if \(f_i = 0\) then \(\eta(f)_i = 1\)
We can easily show that \(\eta\) is injective, surjective and it’s inverse is itself.
Furthermore we can show that \(\eta\) is a group action morphism: $(f g)_i = 1 + (f g)i = 1 + f{g(i)} $ and \((\eta(f) \bullet g)_i = \eta(f)_{g(i)} = 1 + f_{g(i)}\)
In particular \(\eta\) is a bijection between beats.
Assuming each slot can be either 0 or 1 then we have 2^6 = 64 different records.
We can classify the beats by the number of records they contain.
|O|.|Stab| = 6 So the size of the beats is either 1, 2, 3 or 6.
Let B be a bit of size 1 and f the only recording inside that beat. Then we have \[p.f = f \implies p.f(1) = f(1) \implies f(2) = f(1)\] Duplicating this with p2, a, ap, ap2 yields respectively f(3) = f(1), f(4) = f(1), f(5) = f(1), f(6) = f(1).
In the end we have shown that f is constant which means f = 0 or f = 1. Both solution works so we have shown that there are exactly 2 beats of size 1.
0 0 0 0 0 0 and
1 1 1 1 1 1
Let B be a bit of size 2. We can write B = {f, g}. We have |Stab(f)| = 3 so Stab(f) = {e, p, p2}. And similarly for g.
\(pf = f \textrm{ and } p^2f = f \implies \\f(1) = f(2) = f(3) \textrm{ and } f(4) = f(5) = f(6)\)
So f is of the form (x,x,x,y,y,y). Furthermore we must have \(x \neq y\) because otherwise B would have size 1. So finally f is one of:
0 0 0 1 1 1
1 1 1 0 0 0
Both of those have size 2, and they belong to the same beat. So there is exactly 1 beat of size 2
Let B be a bit of size 2.
f a record in B. We have |Stab(f)| = 2 so Stab(f) = {e, a} or {e, ap} or {e, ap2}.
Let’s assume Stab(f) = {e, a}. Then a.f = f. If we have also p.f = f Then B has size 1 which is absurd. So we have \(p.f \neq f\) and \(\phi(p)\) has order 3 which means B = {f, pf, p2.f}
a.f = f implies (f(4), f(6), f(5), f(1), f(3), f(2)) = (f(1), f(2), f(3), f(4), f(5), f(6))
So: f(4) = f(1), f(5) = f(3), f(6) = f(2)
Furthermore we can’t have f(1) = f(2) = f(3) otherwise f would be constant and the beat would have size 1.
So the analysis says that f is of the form (x, y, z, x, z, y) where x, y, z are not all equal.
For example (1, 0, 0, 1, 0, 0) or (0, 1, 0, 0, 0, 0, 1) or (1, 1, 0, 1, 0, 1)
Let’s assume that f is of this form. Then clearly \(p.f \neq f\) and \(a.f = f\) so Stab(f) = {e, a}. So the beat of f has size 3.
Let g be another function of this form (x’, y’, z’, x’, z’, y’) and suppose g is in O(f). Then g = pf or g = pf2. Let’s assume g = pf. Then g = (z, x, y, y, x, z)
So we can deduce z = y: f = (x, y, y, x, y, y) and g = (y, x, y, y, x, y) Furthermore we still have a.g = g so in particular g(5) = g(3) which means x = y. So in the end x = y = z which is absurd. So that means g is not in O(f).
Total number of beats is the total number of triplets (x, y, z) minus the 2 constant triplets \(2*2*2 - 2 = 6\). So there are 6 beats of size 2. They are:
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 0
0 1 1 0 1 1
1 0 1 1 1 0
1 1 0 1 0 1
Let n be the number of 6 beats. We have \(64 = 2 + 1*2 + 6*3 + n*6\) so n = 7. We can see that the function \(card : f \mapsto \sum_{1 \leq i \leq 6} f(i)\) is a beat invariant. \(\forall g \in S3, f \in Rec, card(g \cdot f) = card(f)\) So we can classify the beats of size 6 by their cardinal.
If a beat has cardinal 0 then it is constant So it cannot be of size 6
If a beat has cardinal 1 Let B be a beat of cardinal size 1. Let f be a recording in B. There is a unique index i that gives the place of the unique 1 in f. We can find an element that acts on f that maps i to 1. For example if i = 4, a will do, if i = 5, ap will do… So we can assume f to be 1 0 0 0 0 0. We can check that the beat of f is of size 6. So there is only 1 beat of cardinal 1 of size 6.
If a beat has cardinal 2 Similar to the previous cardinal. We can always find a beat representent which starts with a 1. That means that there are at most 5 beats: 1 1 0 0 0 0
1 0 1 0 0 0 = p . 1 1 0 0 0 0 1 0 0 1 0 0 Orbit has size 3 (a is in stabilizer)
1 0 0 0 1 0 Orbit has size 3 (ap is in stabilizer)
1 0 0 0 0 1 Orbit has size 3 (ap2 is in stabilizer)
all(apprec(gp)(1, 1, 0, 0, 0, 0) == c(1, 0, 1, 0, 0, 0))
## [1] TRUE
So there is only 1 possible beat of cardinal 2 and size 6. which is: 1 1 0 0 0 0, 0 1 1 0 0 0, 1 0 1 0 0 0, 0 0 0 1 0 1, 0 0 0 0 1 1, 0 0 0 1 1 0
all(apprec(gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 1, 1, 0, 0),
apprec(gp)(1, 1, 0, 0, 0, 1) == c(1, 0, 1, 0, 1, 0),
apprec(gp)(1, 1, 0, 1, 0, 0) == c(1, 0, 1, 0, 0, 1),
apprec(ga*gp)(1, 1, 0, 0, 1, 0) == c(1, 0, 0, 1, 1, 0),
apprec(ga)(1, 1, 0, 1, 0, 0) == c(1, 0, 0, 1, 0, 1),
apprec(ga*gp^2)(1, 1, 0, 0, 0, 1) == c(1, 0, 0, 0, 1, 1))
## [1] TRUE
So we have at most 3 beats of cardinal 3 and size 6. We verify that each of those 3 recording span distinct beats and that they each have size 6
Let B be a beat of cardinal 4, we verify that \(\eta(B)\) is a beat of cardinal 2. Since \(\eta\) is a bijection preserving beats we know that it gives a correspondance between beats of cardinal 2 and beats of cardinal 4. So there is only one beat of cardinal 4. And it is given by: 0 0 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1 1 1 1 0 1 0 <- I like this one
1 1 1 1 0 0
1 1 1 0 0 1
| Beat size | Number |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 6 |
| 6 | 7 |
The action of S3 on S3/<p> is not faithfull. S3/<p> = {{e, p, p2}, {a, b, c}} Any element of <p> is sent to the identity. Any other element is sent to ({e, p, p2} {a, b, c})
There is also an action of S3 on {a, b, c}.
And an action of S3 on <p>
Let \(\phi\) be a transitive, faithfull set action \(S3 \rightarrow S(\mathcal{A})\). Where \(\mathcal{A}\) is any set. We note: \(g \bullet x = \phi(g)(x)\) for \(g \in S3, a \in \mathcal{A}\)
First we would like to show that \(\mathcal{A}\) has 6 elements.
Let \(a_0 \in \mathcal{A}\), we let \(f_{a_0}: S3 \rightarrow \mathcal{A}\) defined by \(f_{a_0}(g) = g \bullet a_0\)
Since the action is transitive \(f_{a_0}\) is surjective. Let’s \(g_1, g_2 \in \mathrm{S3}\). \[f_{a_0}(g_1) = f_{a_0}(g_2) \iff g_1 \bullet a_0 = g_2 \bullet a_0 \iff g_1 g_2^{-1} \bullet a_0 = a_0\]
In all this file G is a finite group and S is a set.
An action is a group morphism \(\phi_1: G \rightarrow Aut(S)\) where S is some set. Let \(\phi_2: G \rightarrow Aut(S2)\) be another group action. 2 action are isomorphic iff there exist a set isomorphism \(f: S \rightarrow S2\) such that \[\forall g \in G, f(\phi_1(g)(x)) = \phi_2(g)(f(x))\]
The next property shows that if we have verified the property on f for \(g_1, g_2 \in G\), then the property holds for \(g_1g_2\). \[f(\phi_1(g_1g_2)(x)) = f(\phi_1(g_1)(\phi_1(g_2)(x))) = \phi_2(g_1)(f(\phi_1(g_2)x)) = \phi_2(g_1)(\phi_2(g_2)(fx)) = \phi_2(g_1g_2)(fx)\]
That means that we only need to verify the property on a set of generators for G.
Let’s show that the action on {1, 2, 3} is isomorphic to the action on {{1, 2}, {1, 3}, {2, 3}} by taking f: 1 -> {2, 3} f: 2 -> {1, 3} f: 3 -> {1, 2}
f(p.1) = f(2) = {1, 3} p.f(1) = p.{2, 3} = {1, 3}
f(p.2) = f(3) = {1, 2} p.f(2) = p.{1, 3} = {1, 2}
f(a.1) = f(2) = {1, 3} a.f(1) = a.{2, 3} = {1, 3}
f(a.3) = f(3) = a.f(3) => f(3) = {1, 2}
f(b.2) = f(2) = b.f(2) => f(2) = {1, 3}
f(c.1) = f(1) = c.f(1) => f(1) = {2, 3}
So f is an isomorphism of actions.
Conjugation by an element creates an automorphism. The conjugation by p has the following effect:
## a^p: (2,3)
## b^p: (1,2)
## c^p: (1,3)
## p^p: (1,2,3)
## p2^p: (1,3,2)
So conj(p) = (a c b)
Here is the conjugation by p2:
## a^p2: (1,3)
## b^p2: (2,3)
## c^p2: (1,2)
## p^p2: (1,2,3)
## p2^p2: (1,3,2)
So conj(p2) = (a b c)
Here is the conjugation by a:
## a^a: (1,2)
## b^a: (2,3)
## c^a: (1,3)
## p^a: (1,3,2)
## p2^a: (1,2,3)
So conj(a) = (b c) (p p2)
Here is the conjugation by b:
## a^b: (2,3)
## b^b: (1,3)
## c^b: (1,2)
## p^b: (1,3,2)
## p2^b: (1,2,3)
So conj(b) = (a c) (p p2)
Here is the conjugation by c:
## a^c: (1,3)
## b^c: (1,2)
## c^c: (2,3)
## p^c: (1,3,2)
## p2^c: (1,2,3)
So conj(c) = (a b)(p p2)
So together with the identity there are 6 inner automorphisms.
We will show that Inner(S3) = S3 conj(a)^2 = e conj(p)^3 = e conj(p)^conj(a) = conj a-1 o conj p o conj a = conj a-1pa = conj p2 = conj(p)^2
Since the generators of Inner(S3) have the same relations as those of S3 we know the 2 groups are isomorphic.
We can show that there are no outer isomorphism. Indeed an automorphism maps elements to elements of the same order. There are thus 2 possibilities for mapping p and 3 possibilities for mapping a. Since a and p generate S3 this 2 images will define uniquely a mapping. There are at most 3*2 automorphisms and according to the previous paragraphs we already have 6 inner automorphisms. So all the automorphism are inner.
Since an automorphism is uniquely defined by its image of the generators a and p we might be able to write them as a matrix. Indeed the reason we are able to write linear operators as matrix is because they are defined by their action on a basis which is a generator set of the whole vector space.
First lets try to write elements of S3 as vectors: we note a = (1, 0) and p = (0, 1) (0, x) * (1, m) = p^x * a * p^m = a * a p^x * a p^m = (1, 2*x+m)
(g1, n1) * (g2, n2) = g1n1g2n2 = g1g2inv(g2)n1g2n2 = g1g2n1^g2n2 = (g1g2, n1^g2*n2)
inv(g1) * (g2, n2) * g1 = inv(g1) * (g2*g1, n2^g1) = (g2^g1, n2^g1) conj(g1) = g1 e e g1